A storage replication service is a managed service in which stored or archived data is duplicated among a number of data storage nodes. This provides a measure of redundancy that can be invaluable if a data storage node fails. To obtain storage replication services, including data object storage and replication, data access, and data removal services, a client computing device typically requests a central server to directly perform the service(s). One reason for this is because the server generally maintains a central data structure to index locations of each stored data object in the system to respective storage devices. As data objects are stored and replicated in the system, the server indexes the storage locations of the corresponding replicas so that they can be subsequently located, managed, removed, and repaired responsive to storage node failures. For example, responsive to losing copies of data objects on a failed storage node, the server refers to the index to verify that the lost data objects are fully replicated in the system. However, a centralized index represents a scalability and performance bottleneck in systems containing a very large number of data objects.